package org.example.leetCode;

import org.example.entity.ListNode;

/**
 * 2. 两数相加
 * 给你两个 非空 的链表，表示两个非负的整数。
 * 它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
 * 请你将两个数相加，并以相同形式返回一个表示和的链表。
 * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 */
public class Code2 {

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 创建虚拟头节点
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        int carry = 0; // 进位

        // 遍历两个链表或有进位
        while (l1 != null || l2 != null || carry > 0) {
            int x = (l1 != null) ? l1.val : 0;
            int y = (l2 != null) ? l2.val : 0;

            int sum = x + y + carry;
            carry = sum / 10;

            current.next = new ListNode(sum % 10);
            current = current.next;

            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }

        return dummy.next;
    }


    public static void main(String[] args) {
    // 示例1: 2 -> 4 -> 3 表示 342，5 -> 6 -> 4 表示 465，结果应为 807，即 7 -> 0 -> 8
    ListNode l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
    ListNode l2 = new ListNode(5, new ListNode(6, new ListNode(4)));

    ListNode result1 = addTwoNumbers(l1, l2);

    printList(result1); // 输出: 7 -> 0 -> 8

    // 示例2: 9 -> 9 -> 9 表示 999，9 -> 9 表示 99，结果应为 1098，即 8 -> 9 -> 0 -> 1
    ListNode l3 = new ListNode(9, new ListNode(9, new ListNode(9)));
    ListNode l4 = new ListNode(9, new ListNode(9));

    ListNode result2 = addTwoNumbers(l3, l4);
    printList(result2); // 输出: 8 -> 9 -> 0 -> 1
}

// 打印链表工具方法
public static void printList(ListNode head) {
    while (head != null) {
        System.out.print(head.val + " -> ");
        head = head.next;
    }
    System.out.println("null");
}

}
